package sort;

import java.util.Arrays;

/**
 * @description: 基数排序
 * @title: RadixSort
 * @author: zp
 * @date: 2021/11/20 16:29
 * <p>
 * 最佳案例时间复杂度：Ω(nk)
 * <p>
 * 平均案例时间复杂度：Θ(nk)
 * <p>
 * 最坏案例时间复杂度：O(nk)
 * <p>
 * 空间复杂度：O(n+k)
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {326, 453, 608, 835, 751, 435, 704, 690};
        System.out.println("未排序:" + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
        System.out.println((690 / 1) % 10);
    }

    /**
     * @description: 获取数组中最大值
     * @author: zp
     * @date: 2021/11/24 20:11
     * @param: arr
     * @return: int
     */
    private static int getMax(int[] arr) {
        int n = arr.length;
        int mx = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > mx) {
                mx = arr[i];
            }
        }
        return mx;
    }

    /**
     * @description: 交换位置 排序
     * @author: zp
     * @date: 2021/11/24 20:11
     * @param: arr
     * @param: exp
     * @return: void
     */
    private static void countSort(int[] arr, int exp) {
        //创建一样大的数组 临时保存数据
        int n = arr.length;
        int[] output = new int[n];

        int i;
        //计算每个桶子存放的数据数量
        int[] count = new int[10];
        //初始化所有的值为0
        Arrays.fill(count, 0);

        //取出不同的位数 个 十 百 千 万 ....
        for (i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        //相同于计数排序 把前面桶的数据 递归添加
        for (i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        for (i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        //把排序好的数据复制回原来的数组中
        for (i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }


    public static void radixSort(int[] arr) {
        int m = getMax(arr);
        for (int exp = 1; m / exp > 0; exp *= 10) {
            countSort(arr, exp);
            System.out.println(exp + "位处理:" + Arrays.toString(arr));
        }
    }


}
